// 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
// 示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
// 和回文子串的区别在于
// 回文子序列不是连续的，回文子串是要连续的
// 五部曲
// 1. 确定dp数组以及下标的含义，`dp[i][j]`表示字符串在`[i,j]`内的最长回文子序列的长度
// 2. 确定递推公式
//     1. `s[i] === s[j]`，则`dp[i][j] = dp[i+1][j-1] + 2`
//     2. `s[i] !== s[j]`
//         1. 加入`s[i]`,不要`s[j]`,`dp[i][j-1]`
//         2. 加入`s[j]`,不要`s[i]`,`dp[i+1][j]`
//         3. 则`dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])`
// 3. 初始化，当i等于j的时候，初始化为1，其他情况初始化为0
// ```js
// for(let i=0; i < s.length; i++) {
//     dp[i][i] = 1
// }
// ```
// 4. 确定遍历顺序, 从下到上遍历，从左到右遍历
// 5. 举例推导
// 时间复杂度: O(n^2)
// 空间复杂度: O(n^2)

function longestPalindromeSubseq(s) {
    let dp = new Array(s.length).fill(0).map(_ => new Array(s.length).fill(0))
    for (let i = 0; i < s.length; i++) {
        dp[i][i] =  1       
    }
    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i + 1; j < s.length; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2
            } else {
                // 注意这里，不要s[i]或者不要s[j]的两种情况
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
            }
        }        
    }
    return dp[0][s.length - 1]
}
console.log(longestPalindromeSubseq( "bbbab"))